package com.github.wycm;

import cn.hutool.core.collection.CollectionUtil;
import cn.hutool.core.util.StrUtil;
import cn.hutool.poi.excel.ExcelUtil;
import cn.hutool.poi.excel.ExcelWriter;
import com.gargoylesoftware.htmlunit.html.xpath.XPathUtils;
import org.apache.commons.io.FileUtils;
import org.apache.http.client.CookieStore;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.config.Registry;
import org.apache.http.config.RegistryBuilder;
import org.apache.http.conn.socket.ConnectionSocketFactory;
import org.apache.http.conn.socket.PlainConnectionSocketFactory;
import org.apache.http.conn.ssl.SSLConnectionSocketFactory;
import org.apache.http.impl.client.BasicCookieStore;
import org.apache.http.impl.client.HttpClients;
import org.apache.http.impl.conn.PoolingHttpClientConnectionManager;
import org.apache.http.impl.cookie.BasicClientCookie;
import org.apache.http.ssl.SSLContexts;
import org.jsoup.Jsoup;
import org.jsoup.nodes.Document;
import org.openqa.selenium.By;
import org.openqa.selenium.Cookie;
import org.openqa.selenium.Dimension;
import org.openqa.selenium.WebElement;
import org.openqa.selenium.chrome.ChromeDriver;
import org.openqa.selenium.chrome.ChromeOptions;
import org.openqa.selenium.interactions.Actions;

import javax.imageio.ImageIO;
import javax.net.ssl.SSLContext;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.io.InputStream;
import java.security.KeyStore;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

/**
 * Created by wycm on 2018/9/20.
 * selenium破解腾讯滑动验证码
 */
public class QqCheckCrawler {
    private static String BASE_PATH = "";
    //小方块距离左边界距离，对应到原图的距离
    private static int START_DISTANCE = (22 + 16) * 2;

    private static ChromeDriver driver = null;

    static {
        System.setProperty("webdriver.chrome.driver", "C:\\chromedriver_win32\\chromedriver.exe");
    }

    public static void main(String[] args) {

        Document document = crawl();

    }


    /**
     * 检测qq是否封禁
     * @return
     */
    public static Document crawl() {
        driver = new ChromeDriver();
        List<String> qqList = getQQList();
        List<List> tableInfoList = new LinkedList<List>();

        HashSet<String> splidingError = new HashSet<>();

        for (int i = 0; i < qqList.size(); i++) {
            String qq = qqList.get(i);
            System.out.println("共：" + qqList.size() + "个，当前：" + i);
            final int fi = i;
            try {
                RetryUtils.run(100, 1000, new RetryUtils.RetryTask<Object>() {
                    @Override
                    public Object execute() throws IOException, InterruptedException {


                        return null;
                    }
                });
                List<String> row = new LinkedList<String>();
                driver.manage().window().setSize(new Dimension(1024, 768));
                driver.manage().timeouts().implicitlyWait(5, TimeUnit.SECONDS);
                driver.manage().timeouts().pageLoadTimeout(10, TimeUnit.SECONDS);
                //driver.get("https://007.qq.com/online.html?ADTAG=capt.slide");
                driver.get("https://aq.qq.com/cn2/login_limit/login_limit_index");

                //输入框
                WebElement inputElement = driver.findElement(By.xpath("/html//input"));
                inputElement.sendKeys(qq);
                Thread.sleep(500);


                //点击下一步
                driver.findElement(By.id("next_step")).click();
                Actions actions = new Actions(driver);


                WebElement element;
                //此时已经弹出了滑动校验框，将焦点切换到这里
                driver.switchTo().frame("tcaptcha_iframe");
                String originalUrl = Jsoup.parse(driver.getPageSource()).select("[id=slideBg]").first().attr("src");
                //System.out.println(originalUrl);
                //下载图片
                downloadOriginalImg(fi, originalUrl, driver.manage().getCookies());
                int bgWrapWidth = driver.findElement(By.id("slideBgWrap")).getSize().getWidth();
                int distance = calcMoveDistance(fi, bgWrapWidth);
                List<MoveEntity> list = getMoveEntity(distance);
                element = driver.findElement(By.id("tcaptcha_drag_button"));
                actions.clickAndHold(element).perform();
                int d = 0;
                for (MoveEntity moveEntity : list) {
                    actions.moveByOffset(moveEntity.getX(), moveEntity.getY()).perform();
                    //System.out.println("向右总共移动了:" + (d = d + moveEntity.getX()) + "  sleep：" + moveEntity.getSleepTime());
                    Thread.sleep(moveEntity.getSleepTime());
                }
                actions.release(element).perform();
                Thread.sleep(2 * 1000);

                //在移动之后，还有这个滑动框，说明滑动失败
                WebElement iframe = null;
                try {
                    iframe = driver.findElement(By.id("guideText"));
                } catch (Exception e) {
                    iframe = null;
                }

                //滑动框还在，说明验证失败
                if (iframe != null) {
                    splidingError.add(qq);
                    System.out.println("验证码校验失败，跳过继续");
                    continue;
//                    throw new RuntimeException("验证码滑动失败");
                }

                WebElement nextStep = null;
                try {
                    nextStep = driver.findElement(By.id("next_step"));
                } catch (Exception e) {
                    nextStep = null;
                }
                System.out.printf(qq + "状态: ");

                if (null != nextStep) {
                    System.out.println("正常");
                    //row.add("正常");
                } else {
                    row.add(qq);
                    row.add("封禁");
                    System.out.println("封禁");
                }
                tableInfoList.add(row);

            } catch (Exception e) {
                e.printStackTrace();
            }

        }

        //通过工具类创建writer
        ExcelWriter writer1 = ExcelUtil.getWriter("d:/writeTest.xlsx");
//通过构造方法创建writer
//ExcelWriter writer = new ExcelWriter("d:/writeTest.xls");

//跳过当前行，既第一行，非必须，在此演示用
        writer1.passCurrentRow();

//合并单元格后的标题行，使用默认标题样式

//一次性写出内容，强制输出标题
        writer1.write(tableInfoList);
//关闭writer，释放内存
        writer1.close();

        //通过工具类创建writer
        ExcelWriter writer2 = ExcelUtil.getWriter("d:/error.xlsx");
//通过构造方法创建writer
//ExcelWriter writer = new ExcelWriter("d:/writeTest.xls");

//跳过当前行，既第一行，非必须，在此演示用
        writer2.passCurrentRow();

//合并单元格后的标题行，使用默认标题样式

//一次性写出内容，强制输出标题
        writer2.write(splidingError);
//关闭writer，释放内存
        writer2.close();

//        WebElement webElement = driver.findElement(By.xpath("/html"));
//        String content = webElement.getAttribute("outerHTML");
//        Document document = Jsoup.parse(content);
        return null;

    }

    private static void downloadOriginalImg(int i, String originalUrl, Set<Cookie> cookieSet) throws IOException {
        CookieStore cookieStore = new BasicCookieStore();
        cookieSet.forEach(c -> {
            BasicClientCookie cookie = new BasicClientCookie(c.getName(), c.getValue());
            cookie.setPath(c.getPath());
            cookie.setDomain(c.getDomain());
            cookie.setExpiryDate(c.getExpiry());
            cookie.setSecure(true);
            cookieStore.addCookie(cookie);
        });
        InputStream is = null;
        try {
            SSLContext sslContext = SSLContexts.custom()
                    .loadTrustMaterial(KeyStore.getInstance(KeyStore.getDefaultType())
                            , (chain, authType) -> true).build();
            Registry<ConnectionSocketFactory> socketFactoryRegistry =
                    RegistryBuilder.<ConnectionSocketFactory>create()
                            .register("http", PlainConnectionSocketFactory.INSTANCE)
                            .register("https", new SSLConnectionSocketFactory(sslContext))
                            .build();
            is = HttpClients.custom()
//                    .setProxy(new HttpHost("127.0.0.1", 8888))
                    .setUserAgent("Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/69.0.3497.81 Safari/537.36")
                    .setDefaultCookieStore(cookieStore)
                    .setConnectionManager(new PoolingHttpClientConnectionManager(socketFactoryRegistry))
                    .build()
                    .execute(new HttpGet(originalUrl))
                    .getEntity().getContent();
            FileUtils.copyInputStreamToFile(is, new File(BASE_PATH + "tencent-original" + i + ".png"));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /**
     * 计算小方块需要移动的距离
     *
     * @param i
     * @param bgWrapWidth 背景图片div对应的width
     * @return
     * @throws IOException
     */
    public static int calcMoveDistance(int i, float bgWrapWidth) throws IOException {
        BufferedImage fullBI = ImageIO.read(new File(BASE_PATH + "tencent-original" + i + ".png"));
        for (int w = 340; w < fullBI.getWidth() - 18; w++) {
            int whiteLineLen = 0;
            for (int h = 0; h < fullBI.getHeight(); h++) {
                int[] fullRgb = new int[3];
                fullRgb[0] = (fullBI.getRGB(w, h) & 0xff0000) >> 16;
                fullRgb[1] = (fullBI.getRGB(w, h) & 0xff00) >> 8;
                fullRgb[2] = (fullBI.getRGB(w, h) & 0xff);
                if (isBlack28(fullBI, w, h) && isWhite(fullBI, w, h)) {
                    whiteLineLen++;
                } else {
//                    whiteLineLen = 0;
                    continue;
                }
                if (whiteLineLen >= 50) {
//                    System.out.println("找到缺口成功，实际缺口位置x：" + w);
//                    System.out.println("应该移动距离：" + (w - START_DISTANCE) / (fullBI.getWidth() / bgWrapWidth));
                    return (int) ((w - START_DISTANCE) / (fullBI.getWidth() / bgWrapWidth));
                }
            }

        }
        throw new RuntimeException("计算缺口位置失败");
    }

    /**
     * 当前点的后28个是不是黑色
     *
     * @return 后28个中有80%是黑色返回true, 否则返回false
     */
    private static boolean isBlack28(BufferedImage fullBI, int w, int h) {
        int[] fullRgb = new int[3];
        double blackNum = 0;
        int num = Math.min(fullBI.getWidth() - w, 28);
        for (int i = 0; i < num; i++) {
            fullRgb[0] = (fullBI.getRGB(w + i, h) & 0xff0000) >> 16;
            fullRgb[1] = (fullBI.getRGB(w + i, h) & 0xff00) >> 8;
            fullRgb[2] = (fullBI.getRGB(w + i, h) & 0xff);
            if (isBlack(fullRgb)) {
                blackNum = blackNum + 1;
            }
        }

        return blackNum / num > 0.8;
    }

    /**
     * 当前点是不是白色
     *
     * @param fullBI
     * @param w
     * @param h
     * @return
     */
    private static boolean isWhite(BufferedImage fullBI, int w, int h) {
        int[] fullRgb = new int[3];
        fullRgb[0] = (fullBI.getRGB(w, h) & 0xff0000) >> 16;
        fullRgb[1] = (fullBI.getRGB(w, h) & 0xff00) >> 8;
        fullRgb[2] = (fullBI.getRGB(w, h) & 0xff);

        return isWhite(fullRgb);
    }

    private static boolean isWhite(int[] fullRgb) {
        return (Math.abs(fullRgb[0] - 0xff) + Math.abs(fullRgb[1] - 0xff) + Math.abs(fullRgb[2] - 0xff)) < 125;
    }

    private static boolean isBlack(int[] fullRgb) {
        return fullRgb[0] * 0.3 + fullRgb[1] * 0.6 + fullRgb[2] * 0.1 <= 125;
    }

    /**
     * 默认移动算法
     *
     * @param distance
     * @return
     */
    public static List<MoveEntity> getMoveEntity(int distance) {
        List<MoveEntity> list = new ArrayList<>();
        for (int i = 0; i < distance; i++) {

            MoveEntity moveEntity = new MoveEntity();
            moveEntity.setX(1);
            moveEntity.setY(0);
            moveEntity.setSleepTime(0);
            list.add(moveEntity);
        }
        return list;
    }

    /**
     * 新增的一种移动算法
     *
     * @param distance
     * @return
     */
    public static List<MoveEntity> getMoveEntity1(int distance) {
        List<MoveEntity> list = new ArrayList<>();
        for (int i = 0; i < distance / 5; i++) {
            MoveEntity moveEntity = new MoveEntity();
            moveEntity.setX(5);
            moveEntity.setY(ThreadLocalRandom.current().nextBoolean() ? 10 : -10);
            moveEntity.setSleepTime(10);
            list.add(moveEntity);
        }

        MoveEntity moveEntity = new MoveEntity();
        moveEntity.setX(distance % 5);
        moveEntity.setY(0);
        moveEntity.setSleepTime(10);
        list.add(moveEntity);
        return list;
    }


    private static List<String> getQQList() {
        List<String> qqList = new ArrayList<String>();
//        qqList.add("766097388");
//        qqList.add("1079738530");
        String string = getStr();
        String[] arr = StrUtil.split(string, "\n");
        qqList = CollectionUtil.newArrayList(arr);

        return qqList;
    }

    static String getStr() {
        String str =
                "1517482913\n" +
                        "366585498\n" +
                        "504488512\n" +
                        "2789350449\n" +
                        "3461739010\n" +
                        "465264547\n" +
                        "3307587214\n" +
                        "614388465\n" +
                        "2710627944\n" +
                        "704750081\n" +
                        "2377274205\n" +
                        "3397945178\n" +
                        "3113644151\n" +
                        "198776767\n" +
                        "2497422872\n" +
                        "1073238374\n" +
                        "1666965781\n" +
                        "1026077593\n" +
                        "3469829027\n" +
                        "1521637936\n" +
                        "639911176\n" +
                        "2339701824\n" +
                        "277844722\n" +
                        "1175304006\n" +
                        "1950027212\n" +
                        "3425348396\n" +
                        "1584133901\n" +
                        "2243865873\n" +
                        "379879289\n" +
                        "805723285\n" +
                        "2310053938\n" +
                        "2315053829\n" +
                        "3417205951\n" +
                        "3253718036\n" +
                        "3129188340\n" +
                        "573336703\n" +
                        "1962473138\n" +
                        "417977756\n" +
                        "3530491952\n" +
                        "2548008938\n" +
                        "2833373964\n" +
                        "392969017\n" +
                        "2683506314\n" +
                        "897647389\n" +
                        "2302735448\n" +
                        "2306057916\n" +
                        "2506604302\n" +
                        "283716941\n" +
                        "1968547246\n" +
                        "646927575\n" +
                        "1944489115\n" +
                        "599097474\n" +
                        "478975842\n" +
                        "861998797\n" +
                        "2734894639\n" +
                        "2399753277\n" +
                        "2231053854\n" +
                        "122017896\n" +
                        "166552187\n" +
                        "1840804404\n" +
                        "735035361\n" +
                        "598012920\n" +
                        "434530489\n" +
                        "2372898931\n" +
                        "2811064796\n" +
                        "879577062\n" +
                        "930037903\n" +
                        "3214419769\n" +
                        "1132433173\n" +
                        "212105663\n" +
                        "1296473211\n" +
                        "1725282725\n" +
                        "2323273244\n" +
                        "2723327675\n" +
                        "1293421662\n" +
                        "2032560153\n" +
                        "2549847634\n" +
                        "627138001\n" +
                        "2491549926\n" +
                        "3072509091\n" +
                        "593175830\n" +
                        "741685394\n" +
                        "2261388181\n" +
                        "3094508632\n" +
                        "2902924701\n" +
                        "208963795\n" +
                        "210523508\n" +
                        "157427863\n" +
                        "931570771\n" +
                        "269707623\n" +
                        "2731846353\n" +
                        "584196455\n" +
                        "2437043406\n" +
                        "2491311336\n" +
                        "3055620737\n" +
                        "563217703\n" +
                        "1434321876\n" +
                        "405351965\n" +
                        "648351289\n" +
                        "493613908\n" +
                        "2218706401\n" +
                        "3211294404\n" +
                        "769742418\n" +
                        "859914223\n" +
                        "1040899617\n" +
                        "3241229482\n" +
                        "178635125\n" +
                        "282997621\n" +
                        "1685379382\n" +
                        "1194953773\n" +
                        "1429286791\n" +
                        "2012448951\n" +
                        "1401576489\n" +
                        "993503356\n" +
                        "836470447\n" +
                        "1131034775\n" +
                        "2115774251\n" +
                        "2272664644\n" +
                        "995333874\n" +
                        "1376493093\n" +
                        "345826055\n" +
                        "1853352540\n" +
                        "1319139989\n" +
                        "2456340398\n" +
                        "2973884472\n" +
                        "824420507\n" +
                        "545490079\n" +
                        "2066985747\n" +
                        "1315308170\n" +
                        "3437857285\n" +
                        "334918123\n" +
                        "1003829163\n" +
                        "1759631249\n" +
                        "930734232\n" +
                        "1804914351\n" +
                        "1728751456\n" +
                        "2535675950\n" +
                        "3135889483\n" +
                        "905798600\n" +
                        "2445377925\n" +
                        "1010017501\n" +
                        "2338929304\n" +
                        "2891696790\n" +
                        "925814496\n" +
                        "936757324\n" +
                        "1493231806\n" +
                        "2086526817\n" +
                        "540656961\n" +
                        "3286262182\n" +
                        "3088164581\n" +
                        "3382685087\n" +
                        "286423630\n" +
                        "978370516\n" +
                        "594574000\n" +
                        "844914687\n" +
                        "919961828\n" +
                        "1853985869\n" +
                        "3323878055\n" +
                        "1700463152\n" +
                        "571062660\n" +
                        "2895833598\n" +
                        "1907553078\n" +
                        "1877063246\n" +
                        "1225499547\n" +
                        "1242844697\n" +
                        "2532597645\n" +
                        "825557202\n" +
                        "691353424\n" +
                        "2987168046\n" +
                        "2799476158\n" +
                        "1655237331\n" +
                        "2056735483\n" +
                        "9010061\n" +
                        "1290637010\n" +
                        "508327839\n" +
                        "969534275\n" +
                        "1215422342\n" +
                        "1217247329\n" +
                        "739910760\n" +
                        "2418470842\n" +
                        "1262010512\n" +
                        "2845627593\n" +
                        "3010035047\n" +
                        "758969151\n" +
                        "3480189231\n" +
                        "3087221844\n" +
                        "819017916\n" +
                        "2321425344\n" +
                        "273795672\n" +
                        "595960897\n" +
                        "758569014\n" +
                        "2397525697\n" +
                        "1181217706\n" +
                        "1250721479\n" +
                        "122096980\n" +
                        "809344384\n" +
                        "2451038924\n" +
                        "273992884\n" +
                        "946205792\n" +
                        "3174034832\n" +
                        "379913114\n" +
                        "1395315698\n" +
                        "1072148543\n" +
                        "240245091\n" +
                        "320121066\n" +
                        "1397837426\n" +
                        "178103714\n" +
                        "3483542010\n" +
                        "573631001\n" +
                        "1015791692\n" +
                        "635372859\n" +
                        "247277380\n" +
                        "2570297409\n" +
                        "790409308\n" +
                        "2079769500\n" +
                        "2893475574\n" +
                        "1104337178\n" +
                        "319694525\n" +
                        "1732464599\n" +
                        "2879025255\n" +
                        "532606675\n" +
                        "1528365876\n" +
                        "2380348808\n" +
                        "611655361\n" +
                        "365378685\n" +
                        "402835223\n" +
                        "1712303853\n" +
                        "1752588925\n" +
                        "2175467478\n" +
                        "1469788286\n" +
                        "951234700\n" +
                        "2501071155\n" +
                        "1967809038\n" +
                        "2322685639\n" +
                        "294082438\n" +
                        "1677653953\n" +
                        "546487973\n" +
                        "3428213419\n" +
                        "527500430\n" +
                        "2313233868\n" +
                        "593556575\n" +
                        "207955996\n" +
                        "2776044534\n" +
                        "2430135631\n" +
                        "878903312\n" +
                        "610217878\n" +
                        "476113353\n" +
                        "1060455839\n" +
                        "1092742468\n" +
                        "1940017408\n" +
                        "625201439\n" +
                        "1114599201\n" +
                        "2439261364\n" +
                        "305824217\n" +
                        "1066800964\n" +
                        "3141973210\n" +
                        "315757743\n" +
                        "353303779\n" +
                        "398165756\n" +
                        "2659629530\n" +
                        "2331362225\n" +
                        "1015268562\n" +
                        "2219639376\n" +
                        "1246553462\n" +
                        "312337828\n" +
                        "2496952394\n" +
                        "309291610\n" +
                        "547241875\n" +
                        "3576594252\n" +
                        "1186318310\n" +
                        "3418971836\n" +
                        "1927360020\n" +
                        "1079993889\n" +
                        "3038652374\n" +
                        "254935744\n" +
                        "3042870576\n" +
                        "1141757744\n" +
                        "2528612449\n" +
                        "2036722628\n" +
                        "824135695\n" +
                        "2721581469\n" +
                        "1070728600\n" +
                        "1355248890\n" +
                        "592941242\n" +
                        "1395148049\n" +
                        "759194559\n" +
                        "2522759591\n" +
                        "457921830\n" +
                        "727514588\n" +
                        "893305336\n" +
                        "1770155223\n" +
                        "1633212133\n" +
                        "3420468963\n" +
                        "312057686\n" +
                        "215583648\n" +
                        "1320087378\n" +
                        "2977959926\n" +
                        "2514079109\n" +
                        "524950697\n" +
                        "1596576184\n" +
                        "279942173\n" +
                        "729465927\n" +
                        "1814765987\n" +
                        "2694426932\n" +
                        "1187054035\n" +
                        "1204956330\n" +
                        "2639240167\n" +
                        "1409899086\n" +
                        "568716228\n" +
                        "3446518873\n" +
                        "3596127431\n" +
                        "2735916469\n" +
                        "601041248\n" +
                        "2605685167\n" +
                        "2296604847\n" +
                        "2609350393\n" +
                        "3042615658\n" +
                        "2256138527\n" +
                        "262370246\n" +
                        "1090041539\n" +
                        "2606413216\n" +
                        "3318166670\n" +
                        "1643916762\n" +
                        "597405760\n" +
                        "1839905122\n" +
                        "1241398832\n" +
                        "1060642125\n" +
                        "2033089613\n" +
                        "897665976\n" +
                        "2873519498\n" +
                        "632473153\n" +
                        "982876529\n" +
                        "2945351367\n" +
                        "372001619\n" +
                        "631782209\n" +
                        "1607372931\n" +
                        "850883860\n" +
                        "2845189143\n" +
                        "1193899389\n" +
                        "1911480837\n" +
                        "2298225266\n" +
                        "272162137\n" +
                        "1175656975\n" +
                        "396658251\n" +
                        "1443098235\n" +
                        "1134441660\n" +
                        "3085234320\n" +
                        "1316690244\n" +
                        "3408895776\n" +
                        "972922960\n" +
                        "136689165\n" +
                        "2315695337\n" +
                        "1163258201\n" +
                        "1134844238\n" +
                        "1052008489\n" +
                        "1067003767\n" +
                        "549747199\n" +
                        "17340465\n" +
                        "334899532\n" +
                        "2252432019\n" +
                        "1223469567\n" +
                        "3520308736\n" +
                        "2686445506\n" +
                        "2779367044\n" +
                        "908290665\n" +
                        "1229519574\n" +
                        "892092301\n" +
                        "3519134639\n" +
                        "826512981\n" +
                        "2594728705\n" +
                        "3074570733\n" +
                        "1721544852\n" +
                        "932192316\n" +
                        "972176061\n" +
                        "3166584935\n" +
                        "1362786751\n" +
                        "1634018364\n" +
                        "1293480386\n" +
                        "958972406\n" +
                        "357781216\n" +
                        "1934047423\n" +
                        "3191316314\n" +
                        "2793742593\n" +
                        "171032484\n" +
                        "986276752\n" +
                        "3336716761\n" +
                        "1376595287\n" +
                        "912668171\n" +
                        "1540961584\n" +
                        "822369350\n" +
                        "2268402333\n" +
                        "577855246\n" +
                        "757035870\n" +
                        "443740006\n" +
                        "779334707\n" +
                        "1796586830\n" +
                        "358426775\n" +
                        "215979861\n" +
                        "421809585\n" +
                        "1623512270\n" +
                        "2915924399\n" +
                        "1587588331\n" +
                        "297109873\n" +
                        "310388257\n" +
                        "3179356945\n" +
                        "177966771\n" +
                        "616138292\n" +
                        "2648969630\n" +
                        "2754550961\n" +
                        "3302921975\n" +
                        "3319452909\n" +
                        "1799925879\n" +
                        "954440961\n" +
                        "853870991\n" +
                        "1039004944\n" +
                        "2306255581\n" +
                        "360771102\n" +
                        "2806291017\n" +
                        "2645516357\n" +
                        "3140883058\n" +
                        "1873043428\n" +
                        "1932926468\n" +
                        "3454695166\n" +
                        "2680602356\n" +
                        "1497292030\n" +
                        "2895690334\n" +
                        "2472614316\n" +
                        "1755219998\n" +
                        "1304523485\n" +
                        "909309409\n" +
                        "2583702180\n" +
                        "710476727\n" +
                        "3571719621\n" +
                        "3532089294\n" +
                        "529310219\n" +
                        "2736900200\n" +
                        "81367707\n" +
                        "272126212\n" +
                        "1839819974\n" +
                        "2506164178\n" +
                        "1107528380\n" +
                        "423035314\n" +
                        "2196740898\n" +
                        "1279961992\n" +
                        "605338298\n" +
                        "584854193\n" +
                        "1667887602\n" +
                        "2921126005\n" +
                        "549135329\n" +
                        "2857609378\n" +
                        "1148095714\n" +
                        "2907285923\n" +
                        "644181775\n" +
                        "316943891\n" +
                        "2443070962\n" +
                        "2757324182\n" +
                        "853310772\n" +
                        "1520913783\n" +
                        "2206318157\n" +
                        "1251804196\n" +
                        "2128077233\n" +
                        "2896874226\n" +
                        "2170252959\n" +
                        "2044765554\n" +
                        "1260355816\n" +
                        "2471557794\n" +
                        "2318399574\n" +
                        "2156397284\n" +
                        "2514578091\n" +
                        "471640566\n" +
                        "1193058475\n" +
                        "1841498046\n" +
                        "2397664881\n" +
                        "2564269434\n" +
                        "2285162556\n" +
                        "2223146905\n" +
                        "935357370\n" +
                        "1157059271\n" +
                        "550898797\n" +
                        "3442264297\n" +
                        "1269894113\n" +
                        "1151027974\n" +
                        "1670201823\n" +
                        "2441446232\n" +
                        "2780075987\n" +
                        "471140741\n" +
                        "496946137\n" +
                        "2041056324\n" +
                        "3463283438\n" +
                        "1804400960\n" +
                        "1743777569\n" +
                        "2634336745\n" +
                        "3361964442\n" +
                        "2531162817\n" +
                        "953391377\n" +
                        "653579445\n" +
                        "2830845042\n" +
                        "12041832\n" +
                        "1626253481\n" +
                        "2992408605\n" +
                        "1907682355\n" +
                        "215599150\n" +
                        "83457594\n" +
                        "1321575700\n" +
                        "956566452\n" +
                        "1824879408\n" +
                        "122379103\n" +
                        "1811820489\n" +
                        "2309204942\n" +
                        "113353445\n" +
                        "2233247218\n" +
                        "165463369\n" +
                        "3299247746\n" +
                        "247341845\n" +
                        "153586956\n" +
                        "2627093967\n" +
                        "946294291\n" +
                        "2879876251\n" +
                        "673602300\n" +
                        "178938502\n" +
                        "2023172403\n" +
                        "1605227554\n" +
                        "1603827442\n" +
                        "1805809166\n" +
                        "2505937998\n" +
                        "137527777\n" +
                        "1250232819\n" +
                        "270298910\n" +
                        "1332485127\n" +
                        "7299662\n" +
                        "2670350596\n" +
                        "1090519184\n" +
                        "3393039148\n" +
                        "3351676560\n" +
                        "2338960934\n" +
                        "1077782972\n" +
                        "3283797790\n" +
                        "541168418\n" +
                        "1719496080\n" +
                        "1878458599\n" +
                        "574302717\n" +
                        "3301503146\n" +
                        "3535205038\n" +
                        "625555089\n" +
                        "1455116747\n" +
                        "2969611749\n" +
                        "670573452\n" +
                        "402999369\n" +
                        "752174101\n" +
                        "838554574\n" +
                        "287955677\n" +
                        "1990725569\n" +
                        "2785030127\n" +
                        "1040069569\n" +
                        "511232126\n" +
                        "1101449799\n" +
                        "295255105\n" +
                        "971954550\n" +
                        "1186915410\n" +
                        "250761777\n" +
                        "1255617050\n" +
                        "1901695308\n" +
                        "916205416\n" +
                        "237923758\n" +
                        "1551653367\n" +
                        "292879140\n" +
                        "2488982105\n" +
                        "2643917390\n" +
                        "408907103\n" +
                        "120819023\n" +
                        "574787385\n" +
                        "1129279000\n" +
                        "2576700030\n" +
                        "506288654\n" +
                        "2268954095\n" +
                        "2630716130\n" +
                        "2795626872\n" +
                        "609328337\n" +
                        "320295989\n" +
                        "936223671\n" +
                        "3338707059\n" +
                        "31344484\n" +
                        "756738257\n" +
                        "1395328207\n" +
                        "309553544\n" +
                        "744209803\n" +
                        "3114605942\n" +
                        "278196276\n" +
                        "2261182804\n" +
                        "2528813778\n" +
                        "240796417\n" +
                        "360122311\n" +
                        "1817275092\n" +
                        "3110158919\n" +
                        "635261217\n" +
                        "2824424397\n" +
                        "453330522\n" +
                        "441050832\n" +
                        "3051822194\n" +
                        "584597324\n" +
                        "3134064512\n" +
                        "2225984321\n" +
                        "51387535\n" +
                        "2721496375\n" +
                        "841894020\n" +
                        "418139242\n" +
                        "1002535252\n" +
                        "324467304\n" +
                        "1023144977\n" +
                        "1569244305\n" +
                        "1298060936\n" +
                        "405112014\n" +
                        "2567714191\n" +
                        "1041508751\n" +
                        "3084443051\n" +
                        "1427902694\n" +
                        "710314167\n" +
                        "82596926\n" +
                        "290699597\n" +
                        "26158137\n" +
                        "3463826883\n" +
                        "467896556\n" +
                        "3271859416\n" +
                        "2044539738\n" +
                        "657170690\n" +
                        "155090283\n" +
                        "3361225286\n" +
                        "1042190334\n" +
                        "3522556326\n" +
                        "873138147\n" +
                        "1604448396\n" +
                        "3101116848\n" +
                        "1073550054\n" +
                        "2975380699\n" +
                        "1277331221\n" +
                        "1363668190\n" +
                        "1841750384\n" +
                        "1583681484\n" +
                        "2650619289\n" +
                        "1060548952\n" +
                        "3059020062\n" +
                        "2190759384\n" +
                        "498866685\n" +
                        "1003643827\n" +
                        "3488742207\n" +
                        "790517485\n" +
                        "2141483283\n" +
                        "8266463\n" +
                        "960339007\n" +
                        "910360726\n" +
                        "572690042\n" +
                        "3356827462\n" +
                        "3209327082\n" +
                        "3211227923\n" +
                        "3331767218\n" +
                        "1099109564\n" +
                        "1368254328\n" +
                        "441534231\n" +
                        "2636570076\n" +
                        "321223892\n" +
                        "2720491962\n" +
                        "84400523\n" +
                        "2977374691\n" +
                        "317682388\n" +
                        "2604099553\n" +
                        "1580805702\n" +
                        "617759586\n" +
                        "2834924560\n" +
                        "1119619286\n" +
                        "253885410\n" +
                        "26165230\n" +
                        "814497959\n" +
                        "598691140\n" +
                        "151344146\n" +
                        "745112069\n" +
                        "861477026\n" +
                        "3189055956\n" +
                        "331474257\n" +
                        "362277096\n" +
                        "3501872349\n" +
                        "1749104527\n" +
                        "3128642994\n" +
                        "1840261583\n" +
                        "27502670\n" +
                        "798990800\n" +
                        "3439818839\n" +
                        "1264089833\n" +
                        "873969770\n" +
                        "3048164875\n" +
                        "1932059947\n" +
                        "1285469047\n" +
                        "1649113824\n" +
                        "544365773\n" +
                        "2746831063\n" +
                        "121627637\n" +
                        "250459137\n" +
                        "501994061\n" +
                        "993312871\n" +
                        "2709544651\n" +
                        "1042905172\n" +
                        "982259273\n" +
                        "779750012\n" +
                        "1344929741\n" +
                        "420542897\n" +
                        "2205082899\n" +
                        "2573407939\n" +
                        "46562900\n" +
                        "240467077\n" +
                        "1378396945\n" +
                        "2205702571\n" +
                        "1074043978\n" +
                        "295112854\n" +
                        "121946021\n" +
                        "3320552753\n" +
                        "851087819\n" +
                        "1300494728\n" +
                        "2202082884\n" +
                        "1643392784\n" +
                        "1492472455\n" +
                        "3093467206\n" +
                        "3599843694\n" +
                        "695274596\n" +
                        "1583760759\n" +
                        "1763980403\n" +
                        "965095837\n" +
                        "3237414500\n" +
                        "2598897467\n" +
                        "724441461\n" +
                        "853065200\n" +
                        "3080048382\n" +
                        "1058846449\n" +
                        "1617053427\n" +
                        "2369638786\n" +
                        "1944801053\n" +
                        "2848565400\n" +
                        "2691166459\n" +
                        "344418314\n" +
                        "1073827714\n" +
                        "1323390145\n" +
                        "287232080\n" +
                        "2274767985\n" +
                        "749277605\n" +
                        "420221034\n" +
                        "208669563\n" +
                        "1072572822\n" +
                        "357453547\n" +
                        "2523682327\n" +
                        "2985486198\n" +
                        "175278405\n" +
                        "980703298\n" +
                        "616509964\n" +
                        "1839159261\n" +
                        "815810424\n" +
                        "507093218\n" +
                        "2320343542\n" +
                        "3104938691\n" +
                        "744868803\n" +
                        "3133128994\n" +
                        "916762758\n" +
                        "1006286820\n" +
                        "2745923403\n" +
                        "133320733\n" +
                        "1455457478\n" +
                        "872331518\n" +
                        "1447525433\n" +
                        "3437846145\n" +
                        "328972385\n" +
                        "2693316760\n" +
                        "738439998\n" +
                        "1159339296\n" +
                        "1341596478\n" +
                        "273607572\n" +
                        "280190661\n" +
                        "102278778\n" +
                        "3088522408\n" +
                        "941334339\n" +
                        "820067124\n" +
                        "1169528604\n" +
                        "892835448\n" +
                        "928228025\n" +
                        "22382134\n" +
                        "422066786\n" +
                        "584116118\n" +
                        "2829371557\n" +
                        "1025820964\n" +
                        "1767883276\n" +
                        "50129890\n" +
                        "156589241\n" +
                        "1499620878\n" +
                        "513692482\n" +
                        "731811504\n" +
                        "2653319414\n" +
                        "2048136537\n" +
                        "2995143491\n" +
                        "1684335782\n" +
                        "31594246\n" +
                        "452431290\n" +
                        "331911633\n" +
                        "944362189\n" +
                        "1792696770\n" +
                        "582075027\n" +
                        "574390676\n" +
                        "3280853351\n" +
                        "2141932110\n" +
                        "381150950\n" +
                        "2763726409\n" +
                        "362356133\n" +
                        "287485453\n" +
                        "454287452\n" +
                        "2644174206\n" +
                        "849315587\n" +
                        "156853736\n" +
                        "57626441\n" +
                        "1282523549\n" +
                        "3434124367\n" +
                        "3234829563\n" +
                        "2964852553\n" +
                        "66497796\n" +
                        "2981390525\n" +
                        "406182024\n" +
                        "1801289361\n" +
                        "1543467727\n" +
                        "2698640303\n" +
                        "2894816385\n" +
                        "3418576946\n" +
                        "2023073898\n" +
                        "1296739748\n" +
                        "464484424\n" +
                        "2228941373\n" +
                        "10867315\n" +
                        "1794810761\n" +
                        "359084145\n" +
                        "149285878\n" +
                        "3133404570\n" +
                        "3190970954\n" +
                        "2018629257\n" +
                        "3564954436\n" +
                        "1145928318\n" +
                        "27610799\n" +
                        "275090693\n" +
                        "2911259605\n" +
                        "541566054\n" +
                        "1951596987\n" +
                        "2016093551\n" +
                        "2673699700\n" +
                        "1179818127\n" +
                        "1317022998\n" +
                        "961375822\n" +
                        "441897343\n" +
                        "136177381\n" +
                        "2603469353\n" +
                        "964202663\n" +
                        "149803319\n" +
                        "359406835\n" +
                        "363246189\n" +
                        "1969254335\n" +
                        "2871997631\n" +
                        "1123628305\n" +
                        "283078169\n" +
                        "896087271\n" +
                        "2374928416\n" +
                        "2171173588\n" +
                        "531344242\n" +
                        "742790404\n" +
                        "896175245\n" +
                        "2597027668\n" +
                        "281490615\n" +
                        "1185034919\n" +
                        "332970641\n" +
                        "704629241\n" +
                        "184584758\n" +
                        "1051544190\n" +
                        "2716748648\n" +
                        "975020051\n" +
                        "2366487082\n" +
                        "1539500939\n" +
                        "2738933878\n" +
                        "402804617\n" +
                        "1176725645\n" +
                        "952623647\n" +
                        "95578730\n" +
                        "3314050059\n" +
                        "516418472\n" +
                        "362829159\n" +
                        "1071883857\n" +
                        "1665686878\n" +
                        "120309125\n" +
                        "1783975476\n" +
                        "2268683277\n" +
                        "3027449648\n" +
                        "86002921\n" +
                        "3484282725\n" +
                        "1751811284\n" +
                        "906430822\n" +
                        "562092637\n" +
                        "1485834025\n" +
                        "1483552341\n" +
                        "1785304500\n" +
                        "609059214\n" +
                        "945802237\n" +
                        "1609710427\n" +
                        "1515904614\n" +
                        "247770180\n" +
                        "2434265717\n" +
                        "617359608\n" +
                        "512505353\n" +
                        "479197316\n" +
                        "2212691727\n" +
                        "1497167776\n" +
                        "2047721287\n" +
                        "1174735173\n" +
                        "1479013663\n" +
                        "920740720\n" +
                        "942218730\n" +
                        "51871564\n" +
                        "1247306424\n" +
                        "2042968071\n" +
                        "3237826904\n" +
                        "3208048346\n" +
                        "630557877\n" +
                        "996226706\n" +
                        "510723792\n" +
                        "1709629660\n" +
                        "374908525\n" +
                        "649963420\n" +
                        "1978962799\n" +
                        "2016141826\n" +
                        "3088472168\n" +
                        "3199859782\n" +
                        "1310327053\n" +
                        "2730306137\n" +
                        "3463767628\n" +
                        "1585028367\n" +
                        "591774725\n" +
                        "3301127356\n" +
                        "3171630467\n" +
                        "1538122811\n" +
                        "1444709629\n" +
                        "1564131511\n" +
                        "2745877191\n" +
                        "2384068042\n" +
                        "21811430\n" +
                        "3069726768\n" +
                        "1972935188\n" +
                        "43798823\n" +
                        "1057230818\n" +
                        "65981686\n" +
                        "1655711400\n" +
                        "123937811\n" +
                        "2507614503\n" +
                        "2840896067\n" +
                        "2564468002\n" +
                        "1772332886\n" +
                        "476273097\n" +
                        "717070031\n" +
                        "2020850633\n" +
                        "854712972\n" +
                        "1744512844\n" +
                        "842824498\n" +
                        "1369442681\n" +
                        "2698409152\n" +
                        "974685806\n" +
                        "1499185159\n" +
                        "954827183\n" +
                        "459248605\n" +
                        "3429748392\n" +
                        "1564305816\n" +
                        "3050307070\n" +
                        "3280017492\n" +
                        "320536889\n" +
                        "184476462\n" +
                        "871760563\n" +
                        "381809358\n" +
                        "3573640383\n" +
                        "2971828089\n" +
                        "2325648786\n" +
                        "823631755\n" +
                        "3415410140\n" +
                        "1345636936\n" +
                        "1005629134\n" +
                        "895843612\n" +
                        "3516650832\n" +
                        "287872725\n" +
                        "1422608675\n" +
                        "2428708247\n" +
                        "283131096\n" +
                        "64018073\n" +
                        "1182054307\n" +
                        "278856345\n" +
                        "1833939607\n" +
                        "1346755609\n" +
                        "1965329510\n" +
                        "2728839275\n" +
                        "1980386228\n" +
                        "3384153410\n" +
                        "1217502927\n" +
                        "305992234\n" +
                        "3464246320\n" +
                        "554271275\n" +
                        "1462190856\n" +
                        "122454017\n" +
                        "462730883\n" +
                        "3187674136\n" +
                        "2472460654\n" +
                        "363076355\n" +
                        "1330299513\n" +
                        "2282423491\n" +
                        "2708866376\n" +
                        "654569040\n" +
                        "304185358\n" +
                        "355350708\n" +
                        "3528593534\n" +
                        "974017845\n" +
                        "515009813\n" +
                        "799883121\n" +
                        "895207802\n" +
                        "927284176\n" +
                        "1079738530\n" +
                        "972388160\n" +
                        "2804309846\n" +
                        "742857688\n" +
                        "1178523626\n" +
                        "1775723822\n" +
                        "647358841\n" +
                        "747385081\n" +
                        "1752374158\n" +
                        "751923127\n" +
                        "3281760298\n" +
                        "3241418712\n" +
                        "492215750\n" +
                        "1481105280\n" +
                        "575652763\n" +
                        "3457626046\n" +
                        "792318077\n" +
                        "1021361578\n" +
                        "626274524\n" +
                        "1839772103\n" +
                        "673348805\n" +
                        "20505283\n" +
                        "1606465508\n" +
                        "394848478\n" +
                        "734609402\n" +
                        "2352875908\n" +
                        "2459481565\n" +
                        "1822878478\n" +
                        "782227347\n" +
                        "1521115609\n" +
                        "761452719\n" +
                        "1208085348\n" +
                        "3209480474\n" +
                        "674383334\n" +
                        "2474216028\n" +
                        "2408255486\n" +
                        "250405869\n" +
                        "1018744657\n" +
                        "185394482\n" +
                        "2646578089\n" +
                        "3508689702\n" +
                        "1565842911\n" +
                        "945352056\n" +
                        "332310298\n" +
                        "1353122737\n" +
                        "2396280487\n" +
                        "510063773\n" +
                        "1326540481\n" +
                        "82644429\n" +
                        "1589881139\n" +
                        "3271732674\n" +
                        "285904751\n" +
                        "185180741\n" +
                        "3030448514\n" +
                        "2218614454\n" +
                        "2024608520\n" +
                        "246554385\n" +
                        "2655318186\n" +
                        "310681772\n" +
                        "335520007\n" +
                        "3043006323\n" +
                        "2329274374\n" +
                        "2957750135\n" +
                        "147739660\n" +
                        "3403948062\n" +
                        "1784816488\n" +
                        "1415325582\n" +
                        "1218961437\n" +
                        "1305257491\n" +
                        "3217841236\n" +
                        "860424831\n" +
                        "2135687793\n" +
                        "975894262\n" +
                        "136888780\n" +
                        "976351692\n" +
                        "741028063\n" +
                        "1695833866\n" +
                        "382768819\n" +
                        "1271120775\n" +
                        "1326505019\n" +
                        "2256329979\n" +
                        "1449489407\n" +
                        "1753371799\n" +
                        "2533582415\n" +
                        "3206221690\n" +
                        "445621975\n" +
                        "1193560886\n" +
                        "1302825746\n" +
                        "864211596\n" +
                        "3251066238\n" +
                        "2126385322\n" +
                        "1183816961\n" +
                        "2605383553\n" +
                        "1412090895\n" +
                        "1161918541\n" +
                        "476948924\n" +
                        "522208667\n" +
                        "435398366\n" +
                        "150249563\n" +
                        "1334133796\n" +
                        "2562132110\n" +
                        "755975859\n" +
                        "95279860\n" +
                        "407021072\n" +
                        "3470503171\n" +
                        "2819952009\n" +
                        "664507696\n" +
                        "1871331288\n" +
                        "394758237\n" +
                        "2604273499\n" +
                        "2993454975\n" +
                        "1877484937\n" +
                        "2490424591\n" +
                        "1146690433\n" +
                        "3110673265\n" +
                        "317586864\n" +
                        "913880780\n" +
                        "1600048979\n" +
                        "33603314\n" +
                        "3120916696\n" +
                        "3284777403\n" +
                        "350234415\n" +
                        "411209327\n" +
                        "1355240936\n" +
                        "2168808937\n" +
                        "1196898480\n" +
                        "3173340845\n" +
                        "3310659467\n" +
                        "1522375682\n" +
                        "1728739882\n" +
                        "2155629207\n" +
                        "3203728550\n" +
                        "16197695\n" +
                        "292598878\n" +
                        "2377965342\n" +
                        "963474196\n" +
                        "869838311\n" +
                        "480260374\n" +
                        "2532830717\n" +
                        "5448319\n" +
                        "3314864062\n" +
                        "2495513489\n" +
                        "1342996372\n" +
                        "2409355960\n" +
                        "851074187\n" +
                        "1599795129\n" +
                        "452411352\n" +
                        "1137803042\n" +
                        "1697050722\n" +
                        "1415252365\n" +
                        "294629614\n" +
                        "964264683\n" +
                        "383306499\n" +
                        "475595524\n" +
                        "1204961779\n" +
                        "2807946990\n" +
                        "6909102\n" +
                        "3066588668\n" +
                        "935424763\n" +
                        "330569193\n" +
                        "985467165\n" +
                        "2758226024\n" +
                        "4373590\n" +
                        "936458604\n" +
                        "739196342\n" +
                        "953542406\n" +
                        "3131392225\n" +
                        "1055536704\n" +
                        "1294971956\n" +
                        "2523728558\n" +
                        "93618556\n" +
                        "357967356\n" +
                        "2549415791\n" +
                        "1911804360\n" +
                        "343543424\n" +
                        "1419633022\n" +
                        "2839216716\n" +
                        "1574769246\n" +
                        "3593783327\n" +
                        "843902367\n" +
                        "2776643715\n" +
                        "458788395\n" +
                        "3084366489\n" +
                        "448461768\n" +
                        "1051780430\n" +
                        "1020235210\n" +
                        "2405116435\n" +
                        "1451827370\n" +
                        "2642015811\n" +
                        "2486471350\n" +
                        "2781087619\n" +
                        "371316245\n" +
                        "310155486\n" +
                        "969881075\n" +
                        "1127348053\n" +
                        "259578058\n" +
                        "554510413\n" +
                        "3096243063\n" +
                        "2395611316\n" +
                        "794376719\n" +
                        "429726874\n" +
                        "1391123567\n" +
                        "1830066987\n" +
                        "1093793615\n" +
                        "1731447290\n" +
                        "378586233\n" +
                        "3280774405\n" +
                        "417078875\n" +
                        "3595755619\n" +
                        "976150934\n" +
                        "2670176264\n" +
                        "2445255055\n" +
                        "282908371\n" +
                        "932983433\n" +
                        "1015925912\n" +
                        "2046131687\n" +
                        "22708336\n" +
                        "2822772163\n" +
                        "1480595246\n" +
                        "3526272465\n" +
                        "2284483860\n" +
                        "2237435877\n" +
                        "2363343997\n" +
                        "524648987\n" +
                        "2959289278\n" +
                        "919264568\n" +
                        "26625009\n" +
                        "1602512708\n" +
                        "2087835079\n" +
                        "1421981890\n" +
                        "245645404\n" +
                        "2386895094\n" +
                        "3319433825\n" +
                        "764517184\n" +
                        "3536993930\n" +
                        "1161110496\n" +
                        "2589844821\n" +
                        "592936662\n" +
                        "785131304\n" +
                        "1617745194\n" +
                        "369198863\n" +
                        "1346491253\n" +
                        "599575710\n" +
                        "461064135\n" +
                        "594914560\n" +
                        "1359433673\n" +
                        "2948092950\n" +
                        "3260443925\n" +
                        "18278475\n" +
                        "412623912\n" +
                        "2305326482\n" +
                        "295633985\n" +
                        "450414114\n" +
                        "290841985\n" +
                        "2634177157\n" +
                        "2922778712\n" +
                        "573882223\n" +
                        "852424972\n" +
                        "2994385853\n" +
                        "2056504646\n" +
                        "417377205\n" +
                        "1945923013\n" +
                        "3376442513\n" +
                        "2752247211\n" +
                        "1335923220\n" +
                        "1428627610\n" +
                        "2756254824\n" +
                        "175274622\n" +
                        "2598143757\n" +
                        "592926349\n" +
                        "1712352518\n" +
                        "292760573\n" +
                        "1875501355\n" +
                        "1181278958\n" +
                        "839948541\n" +
                        "787759216\n" +
                        "1255383949\n" +
                        "741235748\n" +
                        "2086757589\n" +
                        "3441518311\n" +
                        "1742107220\n" +
                        "790015535\n" +
                        "1070688933\n" +
                        "2937393921\n" +
                        "762597463\n" +
                        "2372843201\n" +
                        "2263660846\n" +
                        "927999690\n" +
                        "877519543\n" +
                        "124216154\n" +
                        "724525560\n" +
                        "2357237160\n" +
                        "2213671981\n" +
                        "230754837\n" +
                        "1666963626\n" +
                        "236260211\n" +
                        "3513821958\n" +
                        "130161052\n" +
                        "1552108622\n" +
                        "2499776743\n" +
                        "1930571659\n" +
                        "407170835\n" +
                        "343961789\n" +
                        "3218589197\n" +
                        "2665396722\n" +
                        "157131817\n" +
                        "2975348019\n" +
                        "3448564588\n" +
                        "2936034633\n" +
                        "487651607\n" +
                        "1481319659\n" +
                        "3126573073\n" +
                        "1669682831\n" +
                        "710999006\n" +
                        "179362556\n" +
                        "1079118975\n" +
                        "75430760\n" +
                        "1707864132\n" +
                        "2894259664\n" +
                        "2179362148\n" +
                        "2536232037\n" +
                        "136949133\n" +
                        "598142724\n" +
                        "2731694795\n" +
                        "1559520183\n" +
                        "709710053\n" +
                        "1878574547\n" +
                        "1705633319\n" +
                        "3243951139\n" +
                        "3248212581\n" +
                        "203224126\n" +
                        "550668817\n" +
                        "2114603763\n" +
                        "1806222963\n" +
                        "1102310524\n" +
                        "921746018\n" +
                        "3120637049\n" +
                        "2977764893\n" +
                        "2187016368\n" +
                        "425586401\n" +
                        "545640790\n" +
                        "513124462\n" +
                        "523386798\n" +
                        "2785441366\n" +
                        "392089753\n" +
                        "2601256091\n" +
                        "469024731\n" +
                        "1981368207\n" +
                        "358525925\n" +
                        "1101867303\n" +
                        "550257465\n" +
                        "18235785\n" +
                        "3062604358\n" +
                        "1431601616\n" +
                        "354212075\n" +
                        "245416786\n" +
                        "624702604\n" +
                        "405906394\n" +
                        "2201369483\n" +
                        "861611492\n" +
                        "2982432452\n" +
                        "2814792231\n" +
                        "1261597636\n" +
                        "752280743\n" +
                        "1973702944\n" +
                        "478305816\n" +
                        "244015384\n" +
                        "3502407682\n" +
                        "736839965\n" +
                        "1477151957\n" +
                        "1994894578\n" +
                        "1634437400\n" +
                        "470091314\n" +
                        "3470866951\n" +
                        "257167594\n" +
                        "2758553988\n" +
                        "345782002\n" +
                        "1581002700\n" +
                        "1041555432\n" +
                        "2681558041\n" +
                        "1124764612\n" +
                        "601713358\n" +
                        "455548147\n" +
                        "483427378\n" +
                        "2456307186\n" +
                        "707374179\n" +
                        "1019597604\n" +
                        "1945863775\n" +
                        "1285455419\n" +
                        "824295010\n" +
                        "1596746575\n" +
                        "2327655195\n" +
                        "465045684\n" +
                        "2482090269\n" +
                        "370742227\n" +
                        "728749723\n" +
                        "734012831\n" +
                        "810607658\n" +
                        "949077379\n" +
                        "582813696\n" +
                        "406985046\n" +
                        "878845247\n" +
                        "692108694\n" +
                        "709828720\n" +
                        "202024008\n" +
                        "320317975\n" +
                        "1906484627\n" +
                        "2522239283\n" +
                        "2964448050\n" +
                        "1160640563\n" +
                        "2656403064\n" +
                        "553250255\n" +
                        "2632977037\n" +
                        "350564037\n" +
                        "2225335490\n" +
                        "1228785012\n" +
                        "53150697\n" +
                        "1551039960\n" +
                        "1724406396\n" +
                        "3205222396\n" +
                        "1730783787\n" +
                        "2396127801\n" +
                        "754183343\n" +
                        "2816043517\n" +
                        "3256248623\n" +
                        "2231977933\n" +
                        "241901986\n" +
                        "772865283\n" +
                        "695812988\n" +
                        "3084773618\n" +
                        "563397132\n" +
                        "2169809659\n" +
                        "226656703\n" +
                        "307168020\n" +
                        "88539379\n" +
                        "122088204\n" +
                        "2122585704\n" +
                        "1007171291\n" +
                        "54003758\n" +
                        "3235043181\n" +
                        "2559105882\n" +
                        "2466732524\n" +
                        "1664348881\n" +
                        "171546513\n" +
                        "1306308391\n" +
                        "1827027556\n" +
                        "874005729\n" +
                        "3245249854\n" +
                        "596662988\n" +
                        "1030161745\n" +
                        "3507995449\n" +
                        "1186480838\n" +
                        "195574544\n" +
                        "2567373883\n" +
                        "195275647\n" +
                        "1937117554\n" +
                        "948836219\n" +
                        "1196991589\n" +
                        "1871951081\n" +
                        "2965042106\n" +
                        "1984202671\n" +
                        "375196081\n" +
                        "87902983\n" +
                        "2514343071\n" +
                        "531322822\n" +
                        "736559669\n" +
                        "79776907\n" +
                        "2205350736\n" +
                        "2686709684\n" +
                        "271730731\n" +
                        "571776520\n" +
                        "1538457307\n" +
                        "3301648015\n" +
                        "2826163923\n" +
                        "2097192666\n" +
                        "2751381917\n" +
                        "1750580244\n" +
                        "2140264208\n" +
                        "2025997152\n" +
                        "569994213\n" +
                        "2401951220\n" +
                        "2267571840\n" +
                        "2528863965\n" +
                        "760114221\n" +
                        "823108573\n" +
                        "505595469\n" +
                        "724352852\n" +
                        "351937813\n" +
                        "714221235\n" +
                        "3263504310\n" +
                        "809186449\n" +
                        "1600979092\n" +
                        "823344076\n" +
                        "158629552\n" +
                        "243492441\n" +
                        "3061065743\n" +
                        "370866055\n" +
                        "2902094052\n" +
                        "729449434\n" +
                        "1684596949\n" +
                        "1270750343\n" +
                        "290915180\n" +
                        "2091682386\n" +
                        "2950049688\n" +
                        "2321328905\n" +
                        "158664420\n" +
                        "399311050\n" +
                        "997624500\n" +
                        "2575255119\n" +
                        "1529438773\n" +
                        "1393005656\n" +
                        "812165887\n" +
                        "3063465915\n" +
                        "342105553\n" +
                        "3408969310\n" +
                        "550799045\n" +
                        "877821785\n" +
                        "2023535135\n" +
                        "1571797843\n" +
                        "3274946960\n" +
                        "1194674385\n" +
                        "1135234792\n" +
                        "278700535\n" +
                        "2859625385\n" +
                        "1464057383\n" +
                        "445003721\n" +
                        "2063483550\n" +
                        "3595506048\n" +
                        "3319265044\n" +
                        "3397291547\n" +
                        "499298911\n" +
                        "2303974061\n" +
                        "1142127575\n" +
                        "1043948777\n" +
                        "770323770\n" +
                        "1006258053\n" +
                        "2367493801\n" +
                        "765223993\n" +
                        "275510704\n" +
                        "623407691\n" +
                        "2788564668\n" +
                        "2646778020\n" +
                        "3070634053\n" +
                        "2442716794\n" +
                        "916430884\n" +
                        "1922259208\n" +
                        "704161198\n" +
                        "631007027\n" +
                        "282680481\n" +
                        "2969944011\n" +
                        "2764822094\n" +
                        "952500885\n" +
                        "3205699482\n" +
                        "505454865\n" +
                        "239378149\n" +
                        "2018432404\n" +
                        "403424182\n" +
                        "1640245339\n" +
                        "2350932085\n" +
                        "1015661567\n" +
                        "1097507546\n" +
                        "2041988072\n" +
                        "547460352\n" +
                        "945848182\n" +
                        "2697320686\n" +
                        "3518545126\n" +
                        "1098865398\n" +
                        "167800170\n" +
                        "2020124784\n" +
                        "1525373490\n" +
                        "2897039007\n" +
                        "2272673957\n" +
                        "1060088595\n" +
                        "1318299912\n" +
                        "2330459612\n" +
                        "169875631\n" +
                        "2375553168\n" +
                        "1053154754\n" +
                        "2901783051\n" +
                        "1531221306\n" +
                        "619583758\n" +
                        "1076832973\n" +
                        "1289472324\n" +
                        "2258203480\n" +
                        "2682966997\n" +
                        "2139479748\n" +
                        "1391438104\n" +
                        "877236837\n" +
                        "451879987\n" +
                        "1795274613\n" +
                        "58980058\n" +
                        "3394456951\n" +
                        "2512997664\n" +
                        "850849466\n" +
                        "765343807\n" +
                        "1802174014\n" +
                        "2822807594\n" +
                        "394601135\n" +
                        "896271280\n" +
                        "11907059\n" +
                        "578131209\n" +
                        "2270433467\n" +
                        "931934321\n" +
                        "3364642684\n" +
                        "2715635036\n" +
                        "2262889947\n" +
                        "381827861\n" +
                        "3075455865\n" +
                        "356692296\n" +
                        "935370504\n" +
                        "3536577772\n" +
                        "1039096508\n" +
                        "2842881912\n" +
                        "3279095189\n" +
                        "907394745\n" +
                        "438531244\n" +
                        "1766965921\n" +
                        "706750681\n" +
                        "1179812613\n" +
                        "3359045076\n" +
                        "747981677\n" +
                        "1280075420\n" +
                        "2085302468\n" +
                        "397945077\n" +
                        "1584415482\n" +
                        "409821214\n" +
                        "444296866\n" +
                        "504036637\n" +
                        "1216194864\n" +
                        "642237934\n" +
                        "1968326905\n" +
                        "3181893992\n" +
                        "1440300454\n" +
                        "2452264968\n" +
                        "2191880206\n" +
                        "958181410\n" +
                        "1215432935\n" +
                        "2861524707\n" +
                        "2668852694\n" +
                        "798940238\n" +
                        "1311259657\n" +
                        "1724916255\n" +
                        "2382029491\n" +
                        "3460623540\n" +
                        "740387090\n" +
                        "1065163214\n" +
                        "736171692\n" +
                        "2425804987\n" +
                        "1393766905\n" +
                        "375594910\n" +
                        "3561080019\n" +
                        "1678218927\n" +
                        "3579594719\n" +
                        "877156706\n" +
                        "3121297495\n" +
                        "3339380\n" +
                        "228906370\n" +
                        "1216320698\n" +
                        "1797407099\n" +
                        "2816886801\n" +
                        "343688638\n" +
                        "798341244\n" +
                        "997730747\n" +
                        "799183012\n" +
                        "2205481648\n" +
                        "2955246558\n" +
                        "2860999609\n" +
                        "910045614\n" +
                        "414135080\n" +
                        "1617788191\n" +
                        "459187310\n" +
                        "1096362115\n" +
                        "657295747\n" +
                        "229492520\n" +
                        "121999331\n" +
                        "1554018339\n" +
                        "958545451\n" +
                        "1925030666\n" +
                        "2149657246\n" +
                        "207135495\n" +
                        "3241590997\n" +
                        "752973908\n" +
                        "3227699841\n" +
                        "594998053\n" +
                        "2387924705\n" +
                        "475467892\n" +
                        "1242452096\n" +
                        "2016908561\n" +
                        "285350788\n" +
                        "3033422409\n" +
                        "1378553568\n" +
                        "406965538\n" +
                        "2307050857\n" +
                        "383631390\n" +
                        "383796145\n" +
                        "1357217531\n" +
                        "1097249841\n" +
                        "1735746886\n" +
                        "19304161\n" +
                        "841801541\n" +
                        "582153453\n" +
                        "3250565399\n" +
                        "3410813986\n" +
                        "419398760\n" +
                        "215352241\n" +
                        "276179200\n" +
                        "390768568\n" +
                        "26415880\n" +
                        "2246776882\n" +
                        "353321121\n" +
                        "2649147148\n" +
                        "2191686304\n" +
                        "3347407291\n" +
                        "983543624\n" +
                        "1948131383\n" +
                        "1193048723\n" +
                        "2418089061\n" +
                        "287191910\n" +
                        "2521566436\n" +
                        "1359588526\n" +
                        "2832695052\n" +
                        "649431674\n" +
                        "1686443893\n" +
                        "2721844515\n" +
                        "2060767927\n" +
                        "2194208817\n" +
                        "2026159241\n" +
                        "442458813\n" +
                        "2242699337\n" +
                        "251048660\n" +
                        "1326242437\n" +
                        "306563863\n" +
                        "450011808\n" +
                        "2557710669\n" +
                        "3159656058\n" +
                        "645382925\n" +
                        "987918187\n" +
                        "1460102475\n" +
                        "471187206\n" +
                        "913331758\n" +
                        "1285615011\n" +
                        "1206508601\n" +
                        "1806153872\n" +
                        "3046493966\n" +
                        "386173850\n" +
                        "1670738344\n" +
                        "1584017099\n" +
                        "1429716100\n" +
                        "3191322529\n" +
                        "3153247966\n" +
                        "1444318866\n" +
                        "3517441138\n" +
                        "3357550030\n" +
                        "2677829791\n" +
                        "1575299132\n" +
                        "258445504\n" +
                        "2320993618\n" +
                        "3461314835\n" +
                        "1551945853\n" +
                        "2183179483\n" +
                        "2470440359\n" +
                        "277829342\n" +
                        "854000158\n" +
                        "3098183894\n" +
                        "1157795260\n" +
                        "1394937784\n" +
                        "2921708835\n" +
                        "2505520684\n" +
                        "2791903989\n" +
                        "2583234377\n" +
                        "3187396205\n" +
                        "613342724\n" +
                        "3344194053\n" +
                        "1661708768\n" +
                        "2282759909\n" +
                        "2494811837\n" +
                        "2222084935\n" +
                        "3389205046\n" +
                        "1260193662\n" +
                        "461007017\n" +
                        "2987152364\n" +
                        "2362194973\n" +
                        "523984707\n" +
                        "2464038610\n" +
                        "232916067\n" +
                        "1701584028\n" +
                        "178367173\n" +
                        "3510493028\n" +
                        "2674023884\n" +
                        "209626117\n" +
                        "206166097\n" +
                        "371495616\n" +
                        "917223209\n" +
                        "814883858\n" +
                        "996230148\n" +
                        "1506589254\n" +
                        "693578993\n" +
                        "2711780010\n" +
                        "2872412053\n" +
                        "3453704512\n" +
                        "3512356085\n" +
                        "2583772612\n" +
                        "945223222\n" +
                        "1520104411\n" +
                        "2435960946\n" +
                        "253660687\n" +
                        "445731277\n" +
                        "410219401\n" +
                        "1721103853\n" +
                        "1215955086\n" +
                        "1669329935\n" +
                        "2371802158\n" +
                        "766907706\n" +
                        "1558504792\n" +
                        "3613476223\n" +
                        "1054930181\n" +
                        "3514923050\n";

        return str;
    }
}
